package com.su.ou.yang;

import com.sun.tools.corba.se.idl.StringGen;

public class Test2 {
    public static void main(String[] args) {
       char[][] board =
                {
                        {'A', 'B', 'C', 'E'},
                        {'S', 'F', 'C', 'S'},
                        {'A', 'D', 'E', 'E'}
                };
        String string = "ABCCEE";
        System.out.println(isExits(board, string));


    }
    public  static boolean isExits(char[][] word,String str){
        char[] array = str.toCharArray();
        for(int i=0;i<word.length;i++){
            for (int j = 0; j <word[i].length ; j++) {
                if(dfs(word,array,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean dfs(char[][] word, char[] array, int i, int j, int i1) {
        if(i>=word.length||i<0||j>=word[0].length||j<0||word[i][j]!=array[i1]){
            return false;
        }
        if(i1== array.length-1){
            return true;
        }
        char temp=word[i][j];
        word[i][j]='.';
        boolean b = dfs(word, array, i - 1, j, i1 + 1) || dfs(word, array, i + 1, j, i1 + 1) ||
                dfs(word, array, i, j + 1, i1 + 1) || dfs(word, array, i, j - 1, i1 + 1);
        word[i][j]=temp;
        return b;

    }

}
